package com.tgy.leetcode;


import java.util.*;

/**
 * @Author: tgy
 * @Date: 1/6/21 10:30 AM
 *
 * https://leetcode-cn.com/problems/evaluate-division/
 *
 */
public class _399_除法求值 {


    private static class Vertex{

        /**
         * 顶点的值
         */
        String val;
        /**
         * 顶点出去的边
         */
        HashSet<Edge> edges;

        public Vertex(String val) {

            edges = new HashSet<>();
            this.val = val;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (!(o instanceof Vertex)) {
                return false;
            }

            Vertex vertex = (Vertex) o;

            return val != null ? val.equals(vertex.val) : vertex.val == null;
        }

        @Override
        public int hashCode() {
            return val != null ? val.hashCode() : 0;
        }

        @Override
        public String toString() {
            return "Vertex{" +
                    "val='" + val + '\'' +
                    ", edges=" + edges +
                    '}';
        }
    }

    /**
     * 判断一条边是否相等，只要两个定点相等就行
     */
    private static class Edge{

        Vertex from;
        Vertex to;
        // 边上面的值
        private double val;

        public Edge(Vertex from, Vertex to, double val) {
            this.from = from;
            this.to = to;
            this.val = val;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (!(o instanceof Edge)) {
                return false;
            }

            Edge edge = (Edge) o;

            if (from != null ? !from.equals(edge.from) : edge.from != null) {
                return false;
            }
            return to != null ? to.equals(edge.to) : edge.to == null;
        }

        @Override
        public int hashCode() {
            int result = from != null ? from.hashCode() : 0;
            result = 31 * result + (to != null ? to.hashCode() : 0);
            return result;
        }

        @Override
        public String toString() {
            return "Edge{"+ from.val + "," + to.val+"}";
        }
    }

    private HashMap<String,Vertex> grap = new HashMap<>();

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {

        /**
         * 添加顶点
         */

        addVetexAndEdge(equations,values);

        double[] results = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {

            results[i] = findVal(queries.get(i).get(0),queries.get(i).get(1));
        }

        return results;
    }

    private double findVal(String from, String to) {

        if (from == null || to == null || from.length() == 0 || to.length() == 0) {

            return -1.0;
        }

        if (!grap.keySet().contains(from) || !grap.keySet().contains(to)) {

            return -1.0;
        }

        if (from.equals(to)){

            return 1.0;
        }

        Vertex vertex = grap.get(from);

        HashSet<Vertex> vistorVertest = new HashSet<>();

        vistorVertest.add(vertex);
        LinkedList<Double> vistVals = new LinkedList();
        if (reversal(vertex,vistorVertest,vistVals,to)) {

            double result = 1;

            for (Double vistVal : vistVals) {

                result *= vistVal;
            }

            return result;
        }

        return -1.0;
    }

    private boolean reversal(Vertex vertex, HashSet<Vertex> vistorVertest, LinkedList<Double> vistVals, String to) {

        for (Edge edge : vertex.edges) {

            if (vistorVertest.contains(edge.to)) {

                continue;
            }
            vistVals.add(edge.val);
            vistorVertest.add(edge.to);
            if (to.equals(edge.to.val)) {

                return true;
            }

            boolean result = reversal(edge.to, vistorVertest, vistVals, to);

            if (result) {

                return result;
            }
            vistVals.removeLast();
        }


        return false;
    }



    private void addVetexAndEdge(List<List<String>> equations, double[] values) {

        for (int i = 0; i < equations.size(); i++) {

            List<String> equation = equations.get(i);

            String firstVertexVal = equation.get(0);
            Vertex firstVertex = null;
            if (grap.containsKey(firstVertexVal)) {

                firstVertex = grap.get(firstVertexVal);
            }else {

                firstVertex = new Vertex(firstVertexVal);
                grap.put(firstVertexVal,firstVertex);
            }


            String secondVertexVal = equation.get(1);

            Vertex secondVertex = null;

            if (grap.containsKey(secondVertexVal)) {

                secondVertex = grap.get(secondVertexVal);
            }else {

                secondVertex = new Vertex(secondVertexVal);
                grap.put(secondVertexVal,secondVertex);
            }

            firstVertex.edges.add(new Edge(firstVertex,secondVertex,values[i]));
            secondVertex.edges.add(new Edge(secondVertex,firstVertex, 1/values[i]));
        }
    }
}
